/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        //使用层序遍历,可以得到每一层的非空节点个数，那么空节点要如何处理呢？可以对每一个节点都进行编号，编号为i
        //的节点左节点为2*i+1，右节点为2*i+2,这样在计算某一层的时候记录当前层编号最大的值和编号最小的值，相减就是
        //宽度
        vector<pair<TreeNode*,unsigned long>> st;
        unsigned long ret = 1;
        st.push_back(make_pair(root,1));
        while(!st.empty())
        {
            vector<pair<TreeNode*,unsigned long>> tmp;
            for(auto& [node,index]:st)
            {
                if(node->left)
                {
                    tmp.push_back(make_pair(node->left,2*index));
                }
                if(node->right)
                {
                    tmp.push_back(make_pair(node->right,2*index+1));
                }
            }
            //然后就可以计算当前st中这一层的宽度了
            ret = max(ret,st.back().second-st[0].second+1);
            st = move(tmp);//去计算tmp层
        }
        return ret;
    }
};